/*
提交链接：https://leetcode.cn/problems/satisfiability-of-equality-equations/submissions/573561636
990. 等式方程的可满足性-中等
完成日期：2024/10/17
并查集
*/

class UnionFind {
public:
    UnionFind(int size) : parent(size) {
        for (int i = 0; i < size; ++i) {
            parent[i] = i; // 初始化每个节点的父节点为自己
        }
    }
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // 路径压缩
        }
        return parent[x];
    }
    void unionSets(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            parent[rootX] = rootY; // 合并两个集合
        }
    }
private:
    vector<int> parent; // 存储父节点
};
class Solution {
public:
    bool equationsPossible(vector<string>& equations) {
        UnionFind uf(26); // 26个小写字母
        // 先处理相等关系
        for (const string& eq : equations) {
            if (eq[1] == '=') {
                uf.unionSets(eq[0] - 'a', eq[3] - 'a');
            }
        }
        // 检查不等关系
        for (const string& eq : equations) {
            if (eq[1] == '!') {
                if (uf.find(eq[0] - 'a') == uf.find(eq[3] - 'a')) {
                    return false; // 违反了不等关系
                }
            }
        }
        return true; // 所有关系均可满足
    }
};